#pragma once
#include "BinaryTree.h"

typedef BTNode* QueueData;

typedef struct QueueNode
{
    struct QueueNode* next;
    QueueData data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

void QueueInit(Queue* q)
{
    assert(q);
    q->head = q->tail = NULL;
    q->size = 0;
}

QNode* BuyQNode(QueueData x)
{
    QNode* NewNode = (QNode*)malloc(sizeof(QNode));
    if (NewNode == NULL)
    {
        perror("malloc fail");
    }

    NewNode->data = x;
    NewNode->next = NULL;

    return NewNode;
}

void QueuePush(Queue* q, QueueData x)
{
    assert(q);

    if (q->head == NULL)
    {
        assert(!q->tail);
        QNode* Node = BuyQNode(x);
        q->head = q->tail = Node;
        q->size++;
    }
    else
    {
        QNode* Node = BuyQNode(x);
        q->tail->next = Node;
        q->tail = Node;
        q->size++;
    }
}

void QueuePop(Queue* q)
{
    assert(q);
    assert(q->size);

    if (q->size == 1)
    {
        free(q->head);
        q->head = q->tail = NULL;
    }
    else
    {
        QNode* next = q->head->next;
        free(q->head);
        q->head = next;
    }

    q->size--;
}

void QueueFree(Queue* q)
{
    assert(q);

    QNode* cur = q->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }

    q->head = q->tail = NULL;
    q->size = 0;

}

bool is_QueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->size == 0;
}

QNode* QueueFront(Queue* pq)
{
    assert(pq);
    assert(!is_QueueEmpty(pq));

    return pq->head;
}
QNode* QueueBack(Queue* pq)
{
    assert(pq);
    assert(!is_QueueEmpty(pq));

    return pq->tail;
}